package easy;

public class Solution_697 {

    public int findShortestSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        int[][] array = new int[max - min + 1][];

        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] - min;
            if (array[index] == null) {
                array[index] = new int[]{1, i, i};
            } else {
                array[index][0]++;
                array[index][2] = i;
            }
            count = Math.max(count, array[index][0]);
        }

        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null && array[i][0] == count) {
                minLength = Math.min(minLength, array[i][2] - array[i][1] + 1);
            }
        }
        return minLength;
    }

    /*public int findShortestSubArray(int[] nums) {
        int max = 0;
        int[] array = new int[50000];
        for (int i = 0; i < nums.length; i++) {
            array[nums[i]]++;
            max = Math.max(max, array[nums[i]]);
        }

        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        Set<Integer> set3 = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] == max) {
                set1.add(i);
                set2.add(i);
                set3.add(i);
            }
        }

        int[] beginArr = new int[50000];
        int[] endArr = new int[50000];
        for (int i = 0; i < nums.length; i++) {
            if (set1.contains(nums[i])) {
                beginArr[nums[i]] = i;
                set1.remove(nums[i]);
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (set2.contains(nums[i])) {
                endArr[nums[i]] = i;
                set2.remove(nums[i]);
            }
        }
        int minLength = Integer.MAX_VALUE;
        for (Integer v : set3) {
            minLength = Math.min(minLength, endArr[v] - beginArr[v] + 1);
        }
        return minLength;
    }*/

    public static void main(String[] args) {
        Solution_697 model = new Solution_697();
//        System.out.println(model.findShortestSubArray(new int[]{1}));
//        System.out.println(model.findShortestSubArray(new int[]{1, 2, 2, 3, 1}));
//        System.out.println(model.findShortestSubArray(new int[]{1, 2, 2, 3, 1, 4, 2}));
        System.out.println(model.findShortestSubArray(new int[]{49999,1,1,1,2,1}));
    }
}
